package 力扣日常刷题.木22二月.第16天222;


/**
 * @author 帅小伙
 * @date 2022/2/22
 * @description
 */
public class Demo132下一个排列 {


    public static void main(String[] args) {
        Demo132下一个排列 test = new Demo132下一个排列();
        test.nextPermutation(new int[]{1,2,3,8,5,7,6,4});
    }

    public void nextPermutation(int[] nums) {
        int n = nums.length;
        if (n <= 1) return;
        int i = n - 2, j = n - 1, k = n - 1;

        // 找到升序对
        while (i >= 0 && nums[i] >= nums[j]) {
            i--;
            j--;
        }// 从后往前找
        if(i >= 0) {
            // 找到比当前大的最小数
            while(nums[i] >= nums[k]) {
                k--;
            }
            //交换两个数
            swap(nums,i,k);
        }
        // 接下来的序列是   大到小   因此需要反转
        reverse(nums,j,n - 1);
    }

    void reverse(int[]nums,int a,int b) {
        while(a < b) {
            swap(nums,a++,b--);
        }
    }

    void swap(int[] nums,int a,int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }

}
